//测试——查找算法
//编译：g++ TestSearch.cpp ../../*/Search.hpp -o test
#ifndef __TESTSEARCH__CPP
#define __TESTSEARCH__CPP

#include<iostream>
#include<cstdlib>
#include<ctime>
#include"../../Algorithm/Search.hpp"

using namespace std;
using namespace NgSiuKei;

void printSearchResult(int val, SearchResult result, double time) {
    cout << "查找值 -> [ " << val << " ]，结果 -> [ " << (result.first?"成功":"失败") << " : " << result.second << " ]，用时 -> [ " << time << " ]毫秒。" << endl;
}

double functionForTernarySearch(double x) {
    // return 0.5-x+2-((2-1)*0.5)/x;
    return (x-1)*(x-1)+2;
}

int main(void) {
    srand(time(0));

    clock_t start, finish;

    const int size = 10;
    int array[size] = {0};
    for(int i=0; i<size; ++i) {
        array[i] = rand()%(size*10)+1;
    }

    cout << "数组：[ ";
    for(int i=0; i<size; ++i) {
        cout << array[i] << ' ';
    }
    cout << ']' << endl;

    int valNum = size*0.3;
    int vals[valNum+1];
    for(int i=0; i<valNum; ++i) {
        vals[i] = array[rand()%10];
    }
    vals[valNum] = rand()%(size*10)+1;
    ++valNum;

    SearchResult results[valNum];
    double durations[valNum];
    for(int i=0; i<valNum; ++i) {
        start = clock();
        // results[i] = linearSearch(array, size, vals[i]); //线性搜索
        // results[i] = sentinelLinearSearch(array, size, vals[i]); //哨兵线性搜索
        // results[i] = binarySearch(array, size, vals[i]); //二分搜索
        // results[i] = oneSidedBinarySearch(array, size, vals[i]); //元二分搜索
        // -----三元搜索
        // results[i] = ternarySearch<double>(functionForTernarySearch, 0, 3);
        // -----
        // results[i] = jumpSearch(array, size, vals[i]); //跳跃搜索
        // -----插值搜索
        // for(int j=0; j<size; ++j) {
        //     array[j] = j+i+1;
        // }
        // for(int i=0; i<valNum; ++i) {
        //     vals[i] = array[rand()%10];
        // }
        // results[i] = interpolationSearch(array, size, vals[i]);
        // cout << "搜索后数组：[ ";
        // for(int i=0; i<size; ++i) {
        //     cout << array[i] << ' ';
        // }
        // cout << ']' << endl;
        // -----
        // results[i] = exponentialSearch(array, size, vals[i]); //指数搜索
        results[i] = fibonacciSearch(array, size, vals[i]); //斐波那契搜索
        finish = clock();
        durations[i] = (double)(finish - start);// / CLOCKS_PER_SEC;
    }


    cout << "搜索后数组：[ ";
    for(int i=0; i<size; ++i) {
        cout << array[i] << ' ';
    }
    cout << ']' << endl;
    for(int i=0; i<valNum; ++i) {
        printSearchResult(vals[i], results[i], durations[i]);
    }
    double average = 0;
    for(int i=0; i<valNum; ++i) {
        average += durations[i]/valNum;
    }
    cout << "平均耗时: [ " << average << " ]毫秒" << endl;

    return 0;
}

#endif